Given a connected graph $G=(V,E)$, the closeness centrality of a vertex $v$is defined as $\frac{n-1}{\sum_{w \in V} d(v,w)}$. This measure is widely usedin the analysis of real-world complex networks, and the problem of selectingthe $k$ most central vertices has been deeply analysed in the last decade.However, this problem is computationally not easy, especially for largenetworks: in the first part of the paper, we prove that it is not solvable intime $\O(|E|^{2-\epsilon})$ on directed graphs, for any constant $\epsilon>0$,under reasonable complexity assumptions. Furthermore, we propose a newalgorithm for selecting the $k$ most central nodes in a graph: weexperimentally show that this algorithm improves significantly both thetextbook algorithm, which is based on computing the distance between all pairsof vertices, and the state of the art. For example, we are able to compute thetop $k$ nodes in few dozens of seconds in real-world networks with millions ofnodes and edges. Finally, as a case study, we compute the $10$ most centralactors in the IMDB collaboration network, where two actors are linked if theyplayed together in a movie, and in the Wikipedia citation network, whichcontains a directed edge from a page $p$ to a page $q$ if $p$ contains a linkto $q$.
展开▼
机译：给定一个连通图$ G =（V，E）$，顶点$ v $的接近中心定义为$ \ frac {n-1} {\ sum_ {w \ in V} d（v，w）} $。该方法被广泛用于现实世界中复杂网络的分析中，并且在最近十年中对选择$ k $最中心顶点的问题进行了深入分析，但是这个问题在计算上并不容易，特别是对于大型网络：在本文的一部分中，我们证明了在合理的复杂度假设下，对于任何常量$ \ epsilon> 0 $，在有向图上的intime $ \ O（| E | ^ {2- \ epsilon}）$是不可解的。此外，我们提出了一种新的算法来选择图中的k个最中心节点：实验表明，该算法显着改善了基于计算所有顶点对之间距离的教科书算法和现有技术。例如，在具有数百万个节点和边缘的现实网络中，我们能够在几十秒内计算出顶部的$ k $个节点。最后，作为一个案例研究，我们计算了IMDB协作网络中10美元的大多数中央角色，如果两个角色在电影中一起播放，则两个角色会链接在一起，而在Wikipedia引文网络中，这两个角色都从$ p $到页面$ q $（如果$ p $包含指向$ q $的链接）。
展开▼
